package com.code.test.second;

import java.util.Arrays;
import java.util.Random;

/***
 * https://www.cnblogs.com/hapjin/p/5368932.html
 *
 * 问题描述：
 *
 * 给定输入N，生成从1开始的：1，2，3，4，......N 一组随机序列，序列中的数不能重复出现。
 *
 * 比如：N=5，合法的随机序列为{4,3,1,5,2} 、{3,1,4,2,5}……非法的序列有{5,4,1,2,1}
 *
 * 来源：《数据结构与算法分析-MAW著  第二章习题2.8》
 *
 *
 *
 * 思路1：
 *
 * 对于数据a[N]而言，当随机生成第i个数a[i]时，确保a[i]在 a[0]至a[i-1]中没有出现过，就把该数放入a[i]，继续生成下一个数a[i+1]
 *
 * 算法复杂度为O(N^2logN)---每生成一个a[i]，需要扫描a[0]...a[i-1]。
 */
public class RandomArray {


    public static Random random = new Random();

    public static void main(String[] args) {
        int[] ret = ran(5);
        System.out.println(Arrays.toString(ret));
    }

    /**
     * 1...n的随机数组
     * @param n
     * @return
     */
    public static int[] random(int n) {
        int[] ret = new int[n];
        for (int i = 0; i < n; i++) {
            ret[i] = i + 1;
        }

        for (int i = 0; i < n; i++) {
            swap(ret, i, random.nextInt(n));
        }
        return ret;
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static int dd(int i, int j) {
        /**
         * nextInt(j-i+1)     [0,j-i+1)
         * nextInt(j-i+1)+i   [i,j-i+i+1) [i,j+1)  [i,j]
         */
        return random.nextInt(j - i + 1) + i;
    }

    public static int[] ran(int n) {
        int[] ret = new int[n];
        for (int i = 1; i < n; i++) {
            while (true) {
                //先生成一个随机数
                ret[i] = dd(i, n);
                //从第一个元素开始看已经生成的，是否重复
                int j = 0;
                for (; j < i; j++) {
                    if (ret[j] == ret[i]) {
                        //如果已经存在
                        break;
                    }
                }
                //退出条件
                if (j == i) {
                    break;
                }
            }
        }
        return ret;
    }
}
